/**
 * 
 */
package com.gragra.sampling.binary;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import com.gragra.sampling.PopulationProbabilityAssigner;
import com.gragra.sampling.ThreadedUniformAccess;
import com.gragra.sampling.sequentialStructure.WordAndTagHolder;
/**
 * @author Christoph Teichmann
 * 15.09.2013
 */
public abstract class BinaryChart extends BinaryStructure
{
	
	/**
	 * @param wth
	 * @param threads
	 * @param cs
	 * @param sampleHead
	 */
	public BinaryChart(WordAndTagHolder wth, int threads, ConvertSample cs, boolean sampleHead)
	{super(wth, threads, cs, sampleHead);}
	/* (non-Javadoc)
	 * @see com.gragra.sampling.binary.BinaryStructure#coreSampling(double, int, com.gragra.sampling.ThreadedUniformAccess, com.gragra.sampling.binary.BinaryAssigner)
	 */
	@Override
	protected void coreSampling(double annealing, int thread,
			ThreadedUniformAccess tua, PopulationProbabilityAssigner ba)
	{
		this.todo.clear();
		this.todo.add(this.getRootPosition());
		this.createChart(annealing,thread,ba);
		for(int i=0;i<this.todo.size();++i)
		{
			int node = this.todo.getInt(i);
			double prob = -ba.makeLogProb(this, thread)*annealing;
			this.store(node,thread);
			double corr = getChartProbability(node,thread);
			this.drawFromChart(node,thread,tua);
			corr -= this.getChartProbability(node,thread);
			prob += ba.makeLogProb(this, thread)*annealing;
			if(Math.log(tua.nextDouble(thread)) >= (prob+corr))
			{this.revert(node,thread);}
			this.extendWithChildren(node,true,thread,this.todo);
			this.extendWithChildren(node,false,thread,this.todo);
		}
		this.clearChart();
	}
	/**
	 * 
	 */
	private final IntArrayList construction = new IntArrayList();
	/**
	 * 
	 * @param node
	 * @param thread
	 * @param tua
	 */
	private void drawFromChart(int node, int thread, ThreadedUniformAccess tua)
	{
		this.draw(node, thread, tua);
		this.construct(this.result, thread);
	}
	/**
	 * @param thread
	 */
	private void construct(IntArrayList from, int thread)
	{
		for(int i=from.size()-4;i>=0;i-=4)
		{
			int node = from.getInt(i);
			this.subsume(from.getInt(i+1), from.getInt(i+2), node, thread);
			this.setHeadDirection(this.getMiddle(node, thread), from.get(i+3)==0, thread);
		}
	}
	/**
	 * @param node
	 * @param thread
	 * @param tua
	 */
	private void draw(int node, int thread, ThreadedUniformAccess tua)
	{
		this.result.clear();
		this.construction.clear();
		this.construction.add(node);
		this.construction.add(this.getFrom(node, thread));
		this.construction.add(this.getTo(node, thread));
		int free = 1;
		for(int i=0;i<this.construction.size();i+=3)
		{
			int n = this.construction.getInt(i);
			int left = this.construction.getInt(i+1);
			int right = this.construction.getInt(i+2);
			int middle = this.drawMiddle(left,right,thread,tua);
			boolean headLeft = false;
			if(this.samplesHead())
			{headLeft = this.drawHeadLeft(left,right,middle,thread,tua);}
			free = extend(free, n, left, right, middle,headLeft);
		}
	}
	/**
	 * 
	 * @param left
	 * @param right
	 * @param middle
	 * @param thread
	 * @param tua 
	 * @return
	 */
	private boolean drawHeadLeft(int left, int right, int middle, int thread, ThreadedUniformAccess tua)
	{
		double probOne = this.getLogLeftProb(left,right,middle,thread);
		double norm = this.getLogNormLeftProb(left,right,middle,thread);
		if(Math.log(tua.nextDouble(thread)) < probOne-norm)
		{return true;}
		else
		{return false;}
	}
	/**
	 * 
	 * @param left
	 * @param right
	 * @param middle
	 * @param thread
	 * @return
	 */
	protected abstract double getLogNormLeftProb(int left, int right, int middle, int thread);
	/**
	 * returns the probability that the head is on the rgiht side of the middle
	 * @param left
	 * @param right
	 * @param middle
	 * @param isLeft
	 * @param thread
	 * @return
	 */
	protected abstract double getLogLeftProb(int left, int right, int middle, int thread);
	/**
	 * @param free
	 * @param n
	 * @param left
	 * @param right
	 * @param middle
	 * @param headLeft 
	 * @return
	 */
	private int extend(int free, int n, int left, int right, int middle, boolean headLeft)
	{
		this.result.add(n);
		if(middle-left==1)
		{this.result.add(left);}
		else
		{
			int next = this.chartNodes.getInt(free++);
			this.result.add(next);
			this.construction.add(next);
			this.construction.add(left);
			this.construction.add(middle);
		}
		if(right-middle==1)
		{this.result.add(middle);}
		else
		{
			int next = this.chartNodes.getInt(free++);
			this.result.add(next);
			this.construction.add(next);
			this.construction.add(middle);
			this.construction.add(right);
		}
		this.result.add(headLeft ? 0 : 1);
		return free;
	}
	/**
	 * @param node
	 * @param thread
	 */
	private void getFreeNodes(int node, int thread)
	{
		this.chartNodes.clear();
		this.chartNodes.add(node);
		for(int i=0;i<this.chartNodes.size();++i)
		{
			int n = this.chartNodes.getInt(i);
			extensionPaired(thread, n, this.chartNodes);
		}
	}
	/**
	 * 
	 */
	private final IntArrayList result = new IntArrayList();
	/**
	 * 
	 * @param left
	 * @param right
	 * @param thread
	 * @param tua
	 * @return
	 */
	protected int drawMiddle(int left, int right, int thread,
			ThreadedUniformAccess tua)
	{
		int middle = left+1;
		double border = tua.nextDouble(thread);
		double norm = this.getLogNormalizer(left, right, thread);
		for(;middle<right;++middle)
		{
			double prob = Math.exp(this.getLogChoiceProb(left, right, middle, thread)-norm);
			border -= prob;
			if(border <= 0.0)
			{break;}
		}
		if(border > 0)
		{throw new IllegalStateException("wrong normalizer");}
		return middle;
	}
	/**
	 * 
	 */
	private final IntArrayList chartNodes = new IntArrayList();
	/**
	 * 
	 * @param node
	 * @param thread
	 * @return
	 */
	private double getChartProbability(int node, int thread)
	{
		this.construction.clear();
		this.construction.add(node);
		double ret = 0.0;
		for(int i=0;i<this.construction.size();++i)
		{
			int n = this.construction.getInt(i);
			int from = this.getFrom(n, thread);
			int to = this.getTo(n, thread);
			int middle = this.getMiddle(n, thread);
			ret -= this.getLogNormalizer(from,to,thread);
			ret += this.getLogChoiceProb(from,to, middle, thread);
			if(this.samplesHead())
			{
				boolean l = this.getHeadLeft(middle, thread);
				double val = this.getLogLeftProb(from, to, middle, thread)-this.getLogNormLeftProb(from, to, middle, thread);
				if(!l)
				{val = Math.log(1.0-Math.exp(val));}
				ret += val;
			}
			extensionPaired(thread, n, this.construction);
		}
		return ret;
	}
	/**
	 * 
	 * @param from
	 * @param to
	 * @param thread
	 * @return
	 */
	protected abstract double getLogChoiceProb(int from, int to, int middle, int thread);
	/**
	 * 
	 * @param from
	 * @param to
	 * @param thread
	 * @return
	 */
	protected abstract double getLogNormalizer(int from, int to, int thread);
	/**
	 * @param thread
	 * @param n
	 * @param list 
	 */
	private void extensionPaired(int thread, int n, IntArrayList list)
	{
		this.extendWithChildren(n, true, thread, list);
		this.extendWithChildren(n, false, thread, list);
	}
	/**
	 * 
	 * @param annealing
	 * @param thread
	 * @param ba
	 */
	protected abstract void createChart(double annealing, int thread, PopulationProbabilityAssigner ba);
	/**
	 * 
	 * @param node
	 * @param thread
	 */
	private void store(int node, int thread)
	{
		this.storage.clear();
		this.getFreeNodes(node, thread);
		for(int i=0;i<this.chartNodes.size();++i)
		{
			int n = this.chartNodes.getInt(i);
			this.storage.add(n);
			this.storage.add(this.getDominated(n, true, thread));
			this.storage.add(this.getDominated(n, false, thread));
			this.storage.add(this.getHeadLeft(this.getMiddle(n, thread), thread) ? 0 : 1);
		}
	}
	/**
	 * 
	 */
	private final IntArrayList storage = new IntArrayList();
	/**
	 * 
	 * @param node
	 * @param thread
	 */
	private void revert(int node, int thread)
	{this.construct(this.storage, thread);}
	/**
	 * 
	 */
	protected abstract void clearChart();
	/**
	 * 
	 * @param node
	 * @param b
	 * @param thread
	 */
	private void extendWithChildren(int node, boolean left, int thread,IntArrayList toExtend)
	{
		int child = this.getDominated(node, left, thread);
		if(child >= this.getLength())
		{toExtend.add(child);}
	}
	/**
	 * 
	 */
	private final IntArrayList todo = new IntArrayList();
}